<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>青蛙过河</title>
</head>
<body>
  <script>
    function fm(stones) {
      let t = stones[stones.length - 1];
      let mySet = new Set(stones)
      let cache = {}
      let dfs = (prePos, k) => {
        let key = prePos + '->' + k
        if (key in cache) return cache[key]
        if (prePos > t || k == 0) {
          cache[key] = false
          return false
        }
        if (prePos == t) {
          cache[key] = true
          return true
        }
        // 找到[k-1,k,k+1]范围内的所有位置
        for (let i = -1; i < 2; i++) {
          let next = prePos + k + i
          if (mySet.has(next) && dfs(next, k + i)) {
            cache[key] = true
            return true
          }
        }
        cache[key] = false
        return false
      }
      if (!mySet.has(stones[0] + 1)) return false
      return dfs(stones[0] + 1, 1)
    }
    console.log(fn([0, 1, 3, 5, 6, 8, 12, 17]))
  </script>
</body>
</html>